/*
    最小生成树

    前置知识 : 
    讲解025、026、027 - 堆的内容
    讲解056、057 - 并查集的内容
    讲解059~讲解065都是【必备】课程有关图的内容，建议从头开始学习

    最小生成树：在 无向带权图 中选择择一些边，在 保证联通性 的情况下，边的总权值最小

    最小生成树可能不只一棵，只要保证边的总权值最小，就都是正确的最小生成树

    如果无向带权图有n个点，那么最小生成树一定有n-1条边

    扩展：最小生成树一定是最小瓶颈树（题目5）

    注意：最小生成树扩展很多，除了这节课讲的，大部分都是比赛需要的内容，有兴趣可以继续研究

    ================================================

    Kruskal算法（最常用）
    1 把所有的边，根据权值从小到大排序，从权值小的边开始考虑
    2 如果连接当前的边不会形成环，就选择当前的边
    3 如果连接当前的边会形成环，就不要当前的边
    4 考察完所有边之后，最小生成树的也就得到了

    证明略！

    时间复杂度O(m * log m) + O(n) + O(m)

    ================================================

    题目1
    实现Kruskal算法
    返回最小生成树的最小权值和
    测试链接 : https://www.luogu.com.cn/problem/P3366

    ================================================

    Prim算法（不算常用）
    1 解锁的点的集合叫set（普通集合）、解锁的边的集合叫heap（小根堆）。set和heap都为空。
    2 可从任意点开始，开始点加入到set，开始点的所有边加入到heap
    3 从heap中弹出权值最小的边e，查看边e所去往的点x
    A. 如果x已经在set中，边e舍弃，重复步骤3
    B. 如果x不在set中，边e属于最小生成树，把x加入set，重复步骤3
    4 当heap为空，最小生成树的也就得到了

    证明略！

    时间复杂度O(n + m) + O(m * log m)

    ================================================

    Prim算法的优化（比较难，不感兴趣可以跳过）请一定要对堆很熟悉！
    1 小根堆里放(节点，到达节点的花费)，根据 到达节点的花费 来组织小根堆
    2 小根堆弹出(u节点，到达u节点的花费y)，y累加到总权重上去，然后考察u出发的每一条边
    假设，u出发的边，去往v节点，权重w
    A. 如果v已经弹出过了（发现过），忽略该边
    B. 如果v从来没有进入过堆，向堆里加入记录(v, w)
    C. 如果v在堆里，且记录为(v, x)
        1）如果w < x，则记录更新成(v, w)，然后调整该记录在堆中的位置（维持小根堆）
        2）如果w >= x，忽略该边
    3 重复步骤2，直到小根堆为空

    时间复杂度O(n+m) + O((m+n) * log n)

    ================================================

    题目2
    实现Prim算法
    普通版 + 优化版
    返回最小生成树的最小权值和
    测试链接 : https://www.luogu.com.cn/problem/P3366

    ================================================

    题目3
    水资源分配优化
    村里面一共有 n 栋房子。我们希望通过建造水井和铺设管道来为所有房子供水。
    对于每个房子 i，我们有两种可选的供水方案：一种是直接在房子内建造水井
    成本为 wells[i - 1] （注意 -1 ，因为 索引从0开始 ）
    另一种是从另一口井铺设管道引水，数组 pipes 给出了在房子间铺设管道的成本，
    其中每个 pipes[j] = [house1j, house2j, costj] 
    代表用管道将 house1j 和 house2j连接在一起的成本。连接是双向的。
    请返回 为所有房子都供水的最低总成本
    测试链接 : https://leetcode.cn/problems/optimize-water-distribution-in-a-village/

    ================================================

    题目4
    检查边长度限制的路径是否存在
    给你一个 n 个点组成的无向图边集 edges
    其中 edges[i] = [ui, vi, disi] 表示点 ui 和点 vi 之间有一条长度为 disi 的边
    请注意，两个点之间可能有 超过一条边 。
    给你一个查询数组queries ，其中 queries[j] = [pj, qj, limitj]
    你的任务是对于每个查询 queries[j] ，判断是否存在从 pj 到 qj 的路径
    且这条路径上的每一条边都 严格小于 limitj 。
    请你返回一个 布尔数组 answer ，其中 answer.length == queries.length
    当 queries[j] 的查询结果为 true 时， answer 第 j 个值为 true ，否则为 false
    测试链接 : 
    https://leetcode.cn/problems/checking-existence-of-edge-length-limited-paths/

*/